Travelling between cities

5

2 votes
Binary Search, DSU, Data Structures, Dynamic Programming, Medium, Merge Sort, Segment Trees
Problem

You are given positions of cities situated on X axis. The position of the city is denoted by array value .You have a bike which can travel atmost  unit distance once the tank is full and each city has a fuel pump. You can assume that once the bike reaches a city its tank is again filled up completely.Now you have to answer queries where each query is of the following form.

  • :- Find the number of cities lying in the index range that you can reach from the city at index .

Constraints:

Note :- Use fast i/o.

Format of the input file:
First line : i.e Number of testcases.
For each testcase :
First line : Three space separated integers  , and .
Second line : space separated integers denoting the location of cities .
Next lines : Three space separated integers denoting the query.

Format of the output file:
Output the answer to each query in a separate line.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For second query you can reach all the cities from city with location 3(index 2) except the city with location 9(index 4) that lie in the range [1,5] of the array location[i]. Note that X , L and R are indexes of the array.

Editor Image

?